﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Hive.Core;

namespace Hive.NewBot
{
    class Consts
    {
        public class Weights
        {
            public static readonly float Default = 1.0f;
            public static readonly float Food = 1.1f;
        }
    }

    class Bot: IBot
    {
        List<Command> Commands = new List<Command>();
        List<Ant> pool = new List<Ant>();
        List<Command> NewCommands;
        List<Location> ExplorePoints = new List<Location>();
        
        public void DoTurn(GameState state)
        {
            Perf.Start("Total");
            Env.SetState(state);
            Env.Update();
            Log.WriteStatistics();
            LogCommands();
            NewCommands = new List<Command>();
            ProcessEvents();    
            UpdateCommands();
            Log.Write("Commands to execute {0}", Commands.Count);
            ExecuteCommands();
            Perf.End("Total");

            Log.WritePerformance();
        }

        private void LogCommands()
        {
            var str = String.Format("Command count: {0}. Targets: {1}", Commands.Count, Commands.Aggregate("", (a, c) => a + c.Target.ToString()));
            Log.Write(str);
        }

        private void ExecuteCommands()
        {
            var orders = Commands.SelectMany(c => c.Execute());
            Log.Write("{0} orders generated", orders.Count());
            foreach (var o in orders)
            {
                var route = o.Performer.Route.Aggregate("", (a, l) => a + l.ToString());
                Log.Write("Order type {0}, ant [{1}]: {2} to {3}", o.Performer.Command.Type, o.Performer.Ant.Id, o.Performer.Ant.Location, route);
            }
            PerformOrders(orders);
        }

        private void PerformOrders(IEnumerable<Order> orders)
        {
            var graph = BuildMovementGraph(orders);

            ProcessGraph(graph);

            ExecuteGraph(graph, orders);
        }

        private void ProcessGraph(Dictionary<Location, List<Location>> graph)
        {
            // we can have only single child graph but we allow circular references
            List<Location> toProcess = new List<Location>(graph.Where(p => p.Value.Count > 1).Select(p => p.Key));

            while (toProcess.Any())
            {
                var item = toProcess.First();
                var bestChild = FindLongestQueue(graph, item);

                foreach (var c in graph[item].Where(i => i != bestChild))
                {
                    if (!graph.ContainsKey(c))
                        graph[c] = new List<Location>();

                    graph[c].Add(c);
                    toProcess.Add(c);
                }

                graph[item].Clear();
                graph[item].Add(bestChild);

                toProcess.Remove(item);
            }
        }

        private Location FindLongestQueue(Dictionary<Location, List<Location>> graph, Location item)
        {
            var children = graph[item];

            var max = 0;
            Location result = children.First();
            foreach (var c in children)
            {
                var depth = GetDepth(item, c, graph, 1);
                if (depth > max)
                {
                    max = depth;
                    result = c;
                }
            }

            return result;
        }

        private int GetDepth(Location root, Location current, Dictionary<Location, List<Location>> graph, int depth)
        {
            if (current == root)
                return int.MaxValue;

            if (graph.ContainsKey(current))
                return graph[current].Max(l => GetDepth(root, l, graph, depth + 1));
            else
                return depth;
        }

        private void ExecuteGraph(Dictionary<Location, List<Location>> graph, IEnumerable<Order> orders)
        {
            var activeAnts = graph.Where(p => p.Key != p.Value.First()).Select(p => p.Value.First());

            var toExecute = orders.Where(o => activeAnts.Contains(o.Performer.Ant.Location));
            toExecute.ToList().ForEach(o => CarryOutOrder(o));
        }

        private void CarryOutOrder(Order o)
        {
            //Log.Write("Executing order {0} to {1}", o.Performer.Ant.Location, o.Destination);
            o.Performer.Advance();
            //var route = o.Performer.Route.Aggregate("", (a, l) => a + " " + l.ToString());
            //Log.Write("Route after advance {0}", route);

            if (o.Performer.IsComplete())
            {
                var cmd = o.Performer.Command;
                cmd.RemoveAnt(o.Performer.Ant);
                pool.Add(o.Performer.Ant);
                if (!cmd.Performers.Any())
                {
                    Log.Write("Command was removed {0}", cmd.Target);
                    Commands.Remove(cmd);
                    OnCommandEnd(cmd);
                }

                Log.Write("Ant at {0} is returned to pool", o.Performer.Ant.Location);
            }
        }

        private void OnCommandEnd(Command cmd)
        {
            if (cmd.Type == CommandType.Explore)
            {
                ExplorePoints.Add(cmd.Target);
            }
        }

        private Dictionary<Location, List<Location>> BuildMovementGraph(IEnumerable<Order> orders)
        {
            var result = new Dictionary<Location, List<Location>>();

            foreach (var o in orders)
            {
                if (Env.Food.Contains(o.Destination))
                {
                    o.Destination = o.Performer.Ant.Location;
                }

                if (!result.ContainsKey(o.Destination))
                {
                    result[o.Destination] = new List<Location>();
                }

                result[o.Destination].Add(o.Performer.Ant.Location);
            }

            var withoutOrders = Env.MyAnts.Where(a => !orders.Any(o => o.Performer.Ant.Equals(a)));
            foreach (var a in withoutOrders)
            {
                if (!result.ContainsKey(a.Location))
                {
                    result[a.Location] = new List<Location>();
                }

                result[a.Location].Add(a.Location);

            }
            return result;
        }

        private void ProcessEvents()
        {
            Log.Write("Total events for turn: {0}", Env.Events.Count);
            foreach (var e in Env.Events)
            {
                if (e is MyAntAddedEvent)
                {
                    OnAntAdded(e as MyAntAddedEvent);
                }
                else if (e is MyAntRemovedEvent)
                {
                    OnAntRemoved(e as MyAntRemovedEvent);
                }
                else if (e is FoodAddedEvent)
                {
                    OnFoodAdded(e as FoodAddedEvent);
                }
                else if (e is FoodRemovedEvent)
                {
                    OnFoodRemoved(e as FoodRemovedEvent);
                }
            }
        }

        private void OnFoodRemoved(FoodRemovedEvent e)
        {
            var commands = Commands.Where(c => c.Target == e.At).ToList();
            foreach (var c in commands)
            {
                pool.AddRange(c.Performers.Select(p => p.Ant));
                Commands.Remove(c);
                Log.Write("Command was removed {0}", c.Target);
            }
        }

        private void OnFoodAdded(FoodAddedEvent e)
        {
            var c = new Command(CommandType.Food) { Target = e.At, Weight = Consts.Weights.Food };
            //Log.Write("Get food command with target at {0}", e.At);
            NewCommands.Add(c);
        }

        private void OnAntRemoved(MyAntRemovedEvent myAntRemovedEvent)
        {
            Log.Write("Ant removed at {0}", myAntRemovedEvent.Ant.Location);
            var ant = myAntRemovedEvent.Ant;
            if (pool.Contains(ant))
            {
                pool.Remove(ant);
            }
            else
            {
                var c = Commands.Single(cmd => cmd.Performers.Any(p => p.Ant == ant));
                c.RemoveAnt(ant);
            }
        }

        private void OnAntAdded(MyAntAddedEvent myAntAddedEvent)
        {
            pool.Add(myAntAddedEvent.Ant);
            //Log.Write("Ant added at {0}", myAntAddedEvent.Ant.Location);
        }

        private void UpdateCommands()
        {
            ProcessNewCommands();
            AssignNewCommands();
        }

        private void AssignNewCommands()
        {
            var efficiencyMatrix = new int[NewCommands.Count, pool.Count];
            Log.Write("Started AssignNewCommands. Total ants in pool: {0}. Total new commands: {1}", pool.Count, NewCommands.Count);
            CalculateEfficiencies(NewCommands, efficiencyMatrix);

            AssignTasks(efficiencyMatrix);

            //Commands.AddRange(NewCommands.Where(c => c.Performers.Any()));
            Commands = Commands.Union(NewCommands).ToList();

            AssignPool();
        }

        #region Explore behaviour copy-paste with some modification
        private List<Location> GetRoute(bool[,] visited)
        {
            List<Location> route = null;
            var routeLength = int.MaxValue;

            foreach (var ant in pool)
            {
                var r = Env.Map.DirectionTo(ant.Location, l => Env.Map[l] == Tile.Unseen && !visited.At(l));
                if (r.Count < routeLength)
                {
                    route = r;
                    routeLength = r.Count;
                }
            }

            return route;
        }
        private int CalculateTaskLimit()
        {
            double unseenRatio = Env.Map.TileCountUnseen / (double)Env.Map.TileCount;
#warning move this
            var taskLimit = 5;

            var result = 1.0;
            if (unseenRatio > 0.5 && unseenRatio <= 1)
            {
                result = taskLimit * 2 * (1 - unseenRatio);
            }
            else if (unseenRatio >= 0 && unseenRatio <= 0.5)
            {
                result = taskLimit * unseenRatio * 2;
            }

            if ((int)result == 0 && taskLimit == 0)
                result = 1;
            Log.Write("Unseen tiles ratio: {0}. Current explore task limit: {1}", unseenRatio, (int)result);
            return (int)result + 5;
        }
        private void MarkArea(bool[,] visited, Location location, int radius)
        {
            foreach (var offset in Env.GetVisibilityOffsets())
            {
                var l = (location + offset).Normalize();
                visited[l.Row, l.Col] = true;
            }
        }
        #endregion
        

        private void AssignPool()
        {
            AssignExploreCommands();
            AssignPatrolCommands();
        }

        private void AssignPatrolCommands()
        {
            var patrolTargets = Commands.Where(c => c.Type == CommandType.Patrol).Select(c => c.Target);
            int count = pool.Count;

            var targets = ExplorePoints.Except(patrolTargets).ToList();
            if (!targets.Any())
                return;

            for (int i = 0; i < count; i++)
            {
                var t = targets[i % targets.Count];

                var c = Commands.FirstOrDefault(cc => cc.Target == t);
                if (c != null)
                {
                    Log.Write("Added ant {0} to EXISTING PATROL command to {1}", pool[i].Location, c.Target);
                    c.AddAnt(pool[i]);
                }
                else
                {
                    Log.Write("Added ant {0} to NEW PATROL command to {1}", pool[i].Location, t);
                    c = new Command(CommandType.Patrol) { Target = t };
                    c.AddAnt(pool[i]);
                    Commands.Add(c);
                }
            }

            pool.Clear();
        }

        private void AssignExploreCommands()
        {
            var limit = CalculateTaskLimit() - Commands.Count(c => c.Type == CommandType.Explore);
            if (limit <= 0)
                return;

            var targets = new List<Location>();

            bool[,] visited = new bool[Env.Map.Height, Env.Map.Width];

            visited.Iter((i, j, v) => visited[i, j] = Env.Map[i, j] != Tile.Unseen);
            foreach (var ant in pool.ToList())
            {
                var route = Env.Map.DirectionTo(ant.Location, l => NearestUnseen(l));
                //List<Location> route = Env.Map.DirectionTo(ant.Location, l => !visited.At(l) && NearestUnseen(l));
                if (!route.Any())
                {
                    Log.Write("No more routes to unseen tiles. {0} ants remain in pool", pool.Count);
                    break;
                }
                route = route.Take(route.Count - 1).ToList();
                Log.Write("Route Length {0} Explore to {1} destination assigned to [{2}]{3}", route.Count, route.Last().ToString(), ant.Id, ant.Location.ToString());

                var c = Commands.FirstOrDefault(cc => cc.Target == route.Last());
                if (c != null)
                {
                    Log.Write("Existing command");
                    c.AddAnt(ant);
                }
                else
                {
                    Log.Write("NEW command");
                    c = new Command(CommandType.Explore) { Target = route.Last() };
                    c.AddAnt(ant);
                    Commands.Add(c);
                }
                pool.Remove(ant);
                MarkArea(visited, route.Last(), Env.ViewRadius2 / 4);

                if (limit-- <= 0)
                    break;
            }
        }

        private bool NearestUnseen(Location l)
        {
            return Engine.Aim.Values.Select(v => (v + l).Normalize()).Any(v => Env.Map[v] == Tile.Unseen);
        }

        private void AssignTasks(int[,] efficiencyMatrix)
        {
            //TODO: improve calculation
            bool[] processedCommands = new bool[efficiencyMatrix.Height()];
            bool[] processedAnts = new bool[efficiencyMatrix.Width()];
            var removedAnts = new List<Ant>();

            var count = Math.Min(efficiencyMatrix.Height(), efficiencyMatrix.Width());

            while (count > 0)
            {
                var max = Max(efficiencyMatrix, processedAnts, processedCommands);
                if (max == null)
                {
                    Log.Write("Cannot find max in matrix:");
                    Log.WriteEfficiencies(efficiencyMatrix, processedAnts, processedCommands);
                }
                if (efficiencyMatrix.At(max) == 0)
                {
                    processedCommands[max.Row] = true;
                    //Log.Write("Task {0} index {1} has zero efficiency", tasks[max.Row].ToString(), max.Row);
                }
                else
                {
                    processedAnts[max.Col] = true;
                    processedCommands[max.Row] = true;
                    removedAnts.Add(pool[max.Col]);
                    NewCommands[max.Row].AddAnt(pool[max.Col]);
                    Log.Write("Best command {0} index {1} assigned to ant [{2}]{3}", NewCommands[max.Row].Target, max.Row, pool[max.Col].Id, pool[max.Col].Location);
                }
                count--;
            }

            pool = pool.Except(removedAnts).ToList();
        }

        private Location Max(int[,] efficiencyMatrix, bool[] processedAnts, bool[] processedTasks)
        {
            int max = -1;
            Location result = null;
            efficiencyMatrix.Iter((r, c, v) =>
            {
                if (!(processedAnts[c] || processedTasks[r]))
                {
                    if (v > max)
                    {
                        result = new Location(r, c);
                        max = v;
                    }
                }
            }
                );

            return result;
        }

        private void CalculateEfficiencies(List<Command> commands, int[,] efficiencyMatrix)
        {
            for (int t = 0; t < commands.Count; t++)
            {
                var efficiencies = commands[t].CalculateEfficiencies(pool).ToList();
                for (int a = 0; a < efficiencies.Count; a++)
                {
                    efficiencyMatrix[t, a] = efficiencies[a];
                }
            }
        }


        private void ProcessNewCommands()
        {
            NewCommands.AddRange(Commands.Where(c => !c.Performers.Any()));
            //Commands.RemoveAll(c => !c.Performers.Any());
        }
    }
}
